Cryptographic pieces of information such as encrypted messages (“ciphertext”) and signatures are transmitted to recipients over a network or by mail on an electronic storage media. To make the encryption secure, a ciphertext can be considerably longer than the corresponding unencrypted “plaintext”. Likewise, a signature can be considerably longer than the message from which the signature is generated. Therefore, it is desirable to reduce the ciphertext and signature size (“bandwidth”), preferably without compromising the security.
FIGS. 1-5 illustrate ciphertext and signature generation and transfer between computer systems 110 (FIG. 1) interconnected by a network 120. FIG. 2 is a flowchart of an encryption process performed by a system 110 on a “plaintext” message M to obtain a ciphertext c. Before the encryption proper, the message M is encoded into a value H(M) (step 210). The encoding may add some padding and/or random bits to the message M in order to make it possible to obtain different encoded messages H(M), and hence different ciphertexts c, for the same message M in different encryption operations. This will make it harder for an attacker to guess (“invert”) the decryption method if the attacker intercepts different ciphertexts obtained with the same encryption method.
The encoded message H(M) is encrypted at step 220 to obtain the ciphertext c. The ciphertext is transmitted at step 230 over network 120 to another system 110.
The decryption process (FIG. 3) is the reverse of the encryption. The ciphertext c is received by the recipient system 110 (step 304) and decrypted to recover the encoded message H(M) (step 310). The encoded message is decoded (step 320) to recover the original message M.
In FIG. 2, the encoding step 210 and the encryption 220 are shown as separate steps because the encoding method 210 and the decoding 320 (FIG. 3) are sometimes made public while the decryption 310 and possibly the encryption 220 rely on secret information (e.g. a secret key). It is also appropriate to use the term “encryption” to denote the combination of steps 210, 220, and to use the term “decryption” for the combination of steps 310, 320, and/or to state that the encoding step 210 and decoding 320 are omitted.
FIG. 4 illustrates signature generation performed by a system 110. A message M is encoded into H(M) at step 410, and the encoded message is processed (“signed”) to obtain a signature s(M) at step 420. The signature s(M) is transmitted to a recipient system 110 over network 120 (step 430). The recipient system 110 verifies the signature as shown in FIG. 5. The signature is received at step 504 and processed at step 510 to recover the encoded message H(M). The encoded message is decoded (step 520) to obtain the original message M and a test is applied to verify that the message M is indeed the message that was signed. For example, the original message can be provided to the recipient system 110 in a separate transmission for comparison with the message recovered at step 520. In some embodiments, the message is not decoded; the verification can be performed without message recovery.
In FIGS. 4 and 5, the encoding step 410 and the decoding step 520 are shown as separate operations, but it is also appropriate to use the term “signing” for the combination of steps 410, 420, and to use the term “verification” for the combination of steps 510, 520, and/or to state that the encoding step 410 and the decoding part of step 520 are omitted.
In a public-key encryption scheme, the keyholder (the user of one of systems 110) possesses two keys: a public one (which may be widely distributed to other parties) and a secret one. To send an encrypted message to the keyholder, the sender (the user of another system 110) uses the keyholder's public key at step 220 of FIG. 2 to encrypt the message, and transmits the ciphertext to the keyholder. The encoding and decoding schemes (steps 210, 320 of FIGS. 2 and 3) may be public. The keyholder uses its secret key at step 320 to decrypt the ciphertext. For the encryption scheme to be secure, it must be infeasible for anyone who does not possess the secret key to decrypt the transmitted ciphertext.
In a public-key signature scheme, the keyholder also uses a public key and a secret key. The keyholder signs a message at step 420 (FIG. 4) by applying its secret key to that message in a specified way. A verifier may confirm that the keyholder has signed the message by applying the keyholder's public key to the signature (at step 510 of FIG. 5), and checking (at step 520) that some specified condition is satisfied. For the signature scheme to be secure, it must be infeasible for anyone who does not possess the keyholder's secret key to “forge” the keyholder's signature on a message that the keyholder has never actually signed.
In a public-key signcryption scheme, the sender (the user of a system 110) signs a message M with the sender's secret key (see step 420 of FIG. 4) and then encrypts the signed message s(M) with the recipient's public key (see step 220 of FIG. 2), preferably in such a way that the signcryption transmission consumes less bandwidth than if the sender had sent a signature and a ciphertext separately. The recipient (at another system 110) decrypts the signcryption with its secret key, and verifies the sender's signature with the sender's public key.
In a public-key aggregate signature scheme, a set of signers {S1, . . . , Sz} with respective public keys {PK1, . . . , PKz} sign the respective messages {M1, . . . , Mz} in such a way that their aggregated signature—i.e., the bit string needed to verify that each signer Si signed the message Mi—is “short,” preferably consuming less bandwidth than if each signer signed its respective message separately. The aggregate signature is verified with the public keys {PK1, . . . , PKz}.
In a public-key ring signature scheme, a signer Si can choose any set of signers{S1, . . . , Sz} of which Si is a member (i.e. Siε{S1, . . . , Sz}), and produce a “ring signature” on a message that will convince a verifier that at least one signer in {S1, . . . , Sz} signed the message, though the verifier will not be able to determine which one. The signer Si therefore has limited anonymity within the “ring” of possible signers. The verifier uses the public keys {PK1, . . . , PKz} to verify the ring signature. Typically, a ring signature with z possible signers is as long as z separate signatures; thus, it is crucial that the underlying signature scheme be bandwidth-efficient.
Diffie and Hellman introduced the notion of public-key encryption and signature schemes in 1976, but were unable to find concrete instantiations. Rivest, Shamir and Adleman proposed the first public-key encryption and signature schemes (now known as “RSA” schemes) in their article, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (Communications of the ACM, v.21 n.2, p. 120-126, 1978), incorporated herein by reference.
Roughly speaking, the RSA encryption scheme is as follows. The keyholder generates a composite (i.e. non-prime) integer modulus N=pq, where p and q are large prime numbers (e.g. 512 bits). The keyholder also computes φ(N)=(p−1)*(q−1). Finally the keyholder computes integers e and d, both greater than 1, such that ed≡1(mod φ(N)). The keyholder publishes (N, e) as its public key, and keeps p, q and d secret.
To encrypt a message M, the sender performs the operations listed immediately below under “LISTING 1”:
Listing 1: RSA Encryption
Express M as an integer m in [0, N−1], and then set the ciphertext c≡me(mod N).
End of Listing 1.
To decrypt the ciphertext, the keyholder performs the following operation:
Listing 2: RSA DecryptionCompute cd≡med≡m(mod N).
End of Listing 2
Notice that the ciphertext is a number in [1, N], and is about log2 N bits long. This description assumes no message encoding, but message encoding can also be used.
For the RSA signature scheme, the keyholder generates its keys as in the RSA encryption. To sign an appropriately encoded message mε[1, N], the keyholder performs the following operation:
Listing 3: RSA SignatureCompute s=md(mod N).
End of Listing 3
A verifier, using the keyholder's public key, can confirm the signature s by performing the following operation:
Listing 4: RSA SIGNATURECheck that se≡m(mod N).
End of Listing 4
Again, the signature is about log2 N bits long.
Rabin proposed slightly different encryption and signature schemes in his article, Digitalized Signatures and Public-Key Functions as Intractable as Factorization (MIT/LCS/TR-212, MIT Laboratory for Computer Science, Massachusetts Institute of Technology, USA 1979), incorporated herein by reference. A keyholder in this scheme generates the modulus N as in RSA, and sets its public key to be (N, e). Encryption is also the same as RSA in that the ciphertext is c=me(mod N) for an appropriately encoded message m. The ciphertext is about log2 N bits. However, Rabin's schemes use the specific value e=2. There are two reasons for this. First, setting e=2 allows very fast encryption and signature verification. Second, setting e=2 allows one to prove that the resulting schemes are hard to break, assuming that factoring the modulus N is hard. The reduction of factoring to Rabin's schemes (using appropriate encoding) is well-known in the art.
Below, a Rabin encryption scheme with OAEP+ message encoding is described. OAEP+ encoding provides provable security, in the random oracle model, against adaptive chosen ciphertexts attacks, assuming that the underlying encryption scheme is hard to break.
The OAEP+ encoding scheme uses three hash functions (at step 210 of FIG. 2), define by the following formulas (1):G:{0,1}k0→{0,1}m,H′:{0,1}m+k0→{0,1}k1, andH:{0,1}m+k1→{0,1}k0,  (1)where m, k0, k1 are predefined positive integer security parameters. For each i, the expression {0, 1}i denotes the set of all strings of zeroes and ones (“bit strings”) of length i. The same expression also denotes the set of all bit strings of any length smaller than or equal to i; if the string length is less than i, the string can be appended with zeroes on the left up to the length i. This H function in formulas (1) is used for an intermediate value for computation of the message encoding and should not be confused with the encoded message H(M) shown at step 210 of FIG. 2. The quantities 2−k0 and 2−k1 should be negligible to obtain higher security, but any positive integers will work. If n=m+k0+k1, N is preferably chosen so that 2n<N<2n+2n−1. To encrypt a message Mε{0, 1}m, the sender performs the following operations:
Listing 5: Rabin-OAEP Encryption Procedure
(Step 210 (FIG. 2) corresponds to Steps 1-3 immediately below.)
1. Picks a random rε{0, 1}k0.
2. Sets s←(G(r)⊕M)∥H′(r∥M) and t←H(s)⊕r. Here the double bar symbol “∥” denotes string concatenation.
3. Sets x←s∥t, an n-bit string (x corresponds to the final encoded value H(M) of step 210 of FIG. 2).
4. Step 220: Computes the ciphertext c←x2(mod N). Here the bit string x is interpreted as a number: for x=x0x1 . . . xn−1, the number is x0+x1*2+ . . . +xn−1*2n−1.
End of Listing 5.
To decrypt, the recipient performs the following operations:
Listing 6: Rabin-OAEP Decryption Procedure
1. Step 310 (FIG. 3): Compute the modular square roots of c modulo N (step 310 of FIG. 3). As is known, since N is a product of two prime numbers, c may have up to four modular square roots x1, X2, X3, X4, where x1=−x2 and x3=−x4. At least one of x1 and x2, and at least one of x3 and x4 will have n or fewer bits. Without loss of generality, let us assume that each of x1 and x3 has n or fewer bits.2. Step 320: The recipient parses each candidate xi (i=1, 3) into si∥ti for siε{0,1}m+k1 and tiε{0,1}k0, and then parses si into si′∥si″ for si′ε{0, 1}m and siε{0,1}k1. For each i=1, 3, the recipient computes ri←ti⊕H(si) and Mi←si′⊕G(ri), and tests whether si″=H″(ri∥Mi). If there is a unique i for which the condition is satisfied, the recipient outputs Mi as the correct plaintext; otherwise (if there is not such i or if the condition is satisfied for both i=1 and i=3), the recipient indicates a decryption failure.
End of Listing 6.
Below, a Rabin signature scheme with message recovery using a full-domain hash is described. The expression “full domain hash” means that the hash functions (1) can have values as long as their maximum values m, k1, k0 respectively. Various approaches to the encoding, and even to computing modular square roots, are possible; the description below is merely one possible approach. Defining the relevant parameters as for the Rabin encryption above with the additional constraint that p≡3(mod 8) and q≡7(mod 8), the signer performs the following operations:
Listing 7: Rabin-OAEP Signature Procedure
Encoding step 410 (FIG. 4) corresponds to steps 1-2 immediately below.
1. Pick a random rε{0, 1}k0.
2. Set s″←H′(r∥M), s′=←G(s″)⊕M and t←H(s″)⊕r.
3. Set y←s′∥s″∥t, an n-bit integer. The value y corresponds to H(M) of FIG. 4.
Signing step 420 (FIG. 4) corresponds to steps 4-11 immediately below.
4. Compute uq←y(q+1)/4(mod q).
5. Set ey←1 if uq2≡y(mod q); else set ey←−1.
6. Compute up←(eyy)(p+1)/4(mod p).
7. Set fy←1 if up2≡eyy(mod p); else set fy←2.
8. Compute vq←fy(3q−5)/4 uq(mod q) and vp←fy(3p−5)/4 up(mod p).
9. Compute w←vq+q(qp−2(vp−vq)mod p).
10. Set x←w if 2w<N; else set x←N−w. The number x is a square root of eyy/fy (mod N).
11. Output the signature (ey,fy, r, x).
End of Listing 7.
The values of 2(3q−5)/4(mod q), 2(3p−5)/4(mod p) and qp−2(mod p) can be precomputed; so, steps 8 and 9 of Listing 7 add little to the signing time. The signature is verified as follows:
Listing 8: Rabin-OAEP Verification Procedure
1. Step 510 (FIG. 5): Compute ytmp←eyfyx2(mod N).
2. Step 520: Confirm that ytmp is n bits, parse ytmp into stmp′∥stmp″∥ttmp, computeMtmp←G(stmp″)⊕stmp″ andrtmp←H(stmp″)⊕+ttmp,and confirm that stmp″=H(rtmp∥Mtmp).
End of Listing 8.
Notice that the message M=Mtmp is recovered during the verification process.
The encryption and signature schemes of Listings 5-8 are as provably secure as factoring (though the proof is omitted in this description). Notice again that, although these schemes are quite efficient computationally, the bit-length of the ciphertexts and signatures is about log2 N. To be secure against modern factoring methods, N should be at least 1024 bits.
A ring signature scheme using Rabin signatures was proposed in the article, How to Leak a Secret, by R. L. Rivest, A. Shamir and Y. Tauman (Proc. Of Asiacrypt 2001, pages 552-565), incorporated herein by reference. Roughly speaking, for signers {S1, . . . , Sz} with public moduli {N1, . . . , Nz}, the article proposes a ring signature as follows:
Listing 9: Ring Signature
The ring signature is (x′1, . . . , x′z), that satisfies the equation:Ck,v(y1, . . . ,yz)=w  (2)where yi=xi′2 (mod Ni), v and w are given bit strings, and C is a “combining function.”
End of Listing 9.
The article recommends the following combining function:Ck,v(y1, . . . , yz)=Ek(yz⊕Ek(yz−1⊕Ek( . . . ⊕Ek(y1⊕v) . . . ))),  (3)where Ek is a symmetric encryption scheme using a key k. (A symmetric encryption scheme uses the same key for both encryption and decryption; a message M is encrypted into a ciphertext Ek(M)).
Their scheme also uses a trick to get around the fact that the moduli Ni may have different bit lengths. Let gi denote the function gi(xi′)=xi′2 (mod Ni). Instead of setting yi=gi(xi′), they define yi with respect to a domain {0, 1}b, where 2b is much larger than any of the moduli—specifically:
Listing 10: Squaring for Ring Signature                For x′i=qiNi+riε[0,2b−1], yi=qiNi+gi(ri) if (qi+1)Ni≦2b and yi=x′i otherwise.        
End of Listing 10.
Here qi is the quotient of the integer division of x′i by Ni, and ri is the remainder. As long as b is sufficiently large, the proportion of all yi for which (qi+1)Ni>2b will be negligible, so that the mapping xi→yi behaves almost indistinguishable from squaring modulo Ni.
With these considerations in mind, the ring signature is generated as follows (assume Si is the “real” signer):
Listing 11: Ring Signature
1. Compute k=H(M), where M is the message to be signed, and H is a hash function.
2. Pick a random vε{0, 1}b.
3. For each j≠i:
3A. Pick random x′jε{0, 1}b for j≠i.
3B. Compute yj as in LISTING 10.
4. Compute yi such that Ek(yz⊕Ek(yz−1⊕Ek( . . . ⊕Ek(y1⊕v) . . . )))=v.
5. Using secret knowledge about Ni, compute x′i such that x′i is mapped into yi by the mapping of Listing 10.
6. Output the ring signature (x′1, . . . , x′z, v).
End of Listing 11.
Regarding step 4, notice thatyz=Ek−1(v)⊕Ek(yz−1⊕Ek( . . . ⊕Ek(y1⊕v) . . . )).  (4)Next notice thatyz−1=Ek−1(yz⊕Ek−1(v))⊕Ek(yz−2⊕Ek( . . . ⊕Ek(y1⊕v))).  (5)In general,yi=Ek−1(yz⊕Ek−1( . . . yi+1⊕Ek−1(v)))⊕Ek(yi−1⊕Ek( . . . ⊕Ek(y1⊕v))),  (6)and the ring signer uses this equation to compute yi from the values of the yj's, j≠i. To compute x′i, the ring signer computes gi−1 (yi), which is essentially just the computation of a modular square root. Some values of yi, in fact about three-quarters of them, do not have modular square roots; in this case, step 3 must be performed again until yi is a quadratic residue modulo Ni.
Listing 12: Ring Signature Verification.
1. Compute k=H(M). For all j, compute the respective values of yj from x′j by inverting the mapping of Listing 10.
2. Confirm thatEk(yz⊕Ek(yz−1⊕Ek( . . . ⊕Ek(y1⊕v) . . . )))=v.  (7)
End of Listing 12.
In the above-described encryption and signature schemes, ciphertexts and signatures are log2 N≧1024 bits long. Long ciphertexts and signatures, such as these, can cause problems—particularly over channels prone to loss, since decryption and signature verification require the complete ciphertext or signature. Also, long ciphertexts and signatures are more likely to encounter problems with packet fragmentation, where the ciphertext or signature is split across more than one packet. Shorter signatures and ciphertexts are also more power efficient to transmit. According to K. Barr and K. Asanovic, Energy Aware Lossless Data Compression (Proc. Of MobiSys 2003), a wireless transmission of a single bit can cost more than 1000 times as much energy as a 32-bit computation. In battery operated computer systems, energy consumption required for a wireless transmission can be a significant bottleneck. Also, signal interference places physical limits on how much data can be transmitted wirelessly by a battery powered system in a given region.
From a security perspective, Rabin's schemes have the very desirable property of being provably as hard to break as factoring, a property that should be retained if possible. Accordingly, there is a need for an encryption scheme that is provably secure assuming the hardness of factoring a log2 N bit modulus, but in which the ciphertexts are considerably shorter than log2 N bits. There is also a need for a provably secure signature scheme in which the signatures are considerably shorter than log2 N bits. Further, the signature scheme should preferably retain the message recovery property of the Rabin signatures.
There is also a need for advanced cryptographic schemes—such as signcryption, aggregate signatures and ring signatures—that are based on factoring, but are more bandwidth efficient than schemes that use extensions of Rabin's encryption and signature schemes.